| 翻訳と辞書 |
Thue number
In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. (2002) and named after mathematician Axel Thue, who studied the squarefree words used to define this number.
Alon et al. define a ''nonrepetitive coloring'' of a graph to be an assignment of colors to the edges of the graph, such that there does not exist any even-length simple path in the graph in which the colors of the edges in the first half of the path form the same sequence as the colors of the edges in the second half of the path. The Thue number of a graph is the minimum number of colors needed in any nonrepetitive coloring.
Variations on this concept involving vertex colorings or more general walks on a graph have been studied by several authors including Barát and Varjú, Barát and Wood (2005), Brešar and Klavžar (2004), and Kündgen and Pelsmajer.
== Example ==
Consider a pentagon, that is, a cycle of five vertices. If we color the edges with two colors, some two adjacent edges will have the same color x; the path formed by those two edges will have the repetitive color sequence xx. If we color the edges with three colors, one of the three colors will be used only once; the path of four edges formed by the other two colors will either have two consecutive edges or will form the repetitive color sequence xyxy. However, with four colors it is not difficult to avoid all repetitions. Therefore, the Thue number of ''C''5 is four.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Thue number」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|